#include <iostream>

using namespace std;

struct ListNode
{
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(NULL) {}
};

class Solution
{
public:
  ListNode *reverseList(ListNode *head)
  {
    ListNode *pre = NULL, *cur = head;
    while (cur)
    {
      ListNode *nex = cur->next;
      cur->next = pre;
      pre = cur;
      cur = nex;
    }
    return pre;
  }
};

ListNode *createLinkedList(int arr[], int n);
void printLinkedList(ListNode *head);
void deleteLinkedList(ListNode *head);

int main(int argc, char const *argv[])
{
  int arr[] = {1, 2, 3, 4, 5};
  int n = sizeof(arr) / sizeof(arr[0]);
  ListNode *list = createLinkedList(arr, n);
  printLinkedList(list);
  list = Solution().reverseList(list);
  printLinkedList(list);
  deleteLinkedList(list);
  return 0;
}

ListNode *createLinkedList(int arr[], int n)
{
  if (n == 0)
    return NULL;
  ListNode *head = new ListNode(arr[0]);
  ListNode *curNode = head;
  for (int i = 1; i < n; ++i)
  {
    curNode->next = new ListNode(arr[i]);
    curNode = curNode->next;
  }
  return head;
}

void printLinkedList(ListNode *head)
{
  ListNode *curNode = head;
  while (curNode != NULL)
  {
    cout << curNode->val << "->";
    curNode = curNode->next;
  }
  cout << "NULL" << endl;
  return;
}

void deleteLinkedList(ListNode *head)
{
  ListNode *curNode = head;
  while (curNode != NULL)
  {
    ListNode *delNode = curNode;
    curNode = curNode->next;
    delete delNode;
  }
  cout << "内存释放结束" << endl;
  return;
}
